package marchingCubes;

import java.awt.geom.Line2D;
import java.util.Vector;

import marchingCubes.MCubeEngine.MCFace;
import marchingCubes.MCubeEngine.MCNode;
import marchingCubes.MCubeEngine.MCube;

import simpleGeom.Bounds3D;
import simpleGeom.Box3D;
import simpleGeom.HasPos3D;
import simpleGeom.Plane;
import simpleGeom.SimpleTriangle;
import simpleGeom.TriangleMath;
import simpleGeom.Vec3D;

public class DualCubeEngine {

	public DualCube[][][] cubes;
	float sX;
	float sY;
	float sZ;
	public float dimX;
	public float dimY;
	public float dimZ;
	public int nX;
	public int nY;
	public int nZ;
	float scale;
	public void init(Box3D b, float dim) {
		sX = b.x1;
		sY = b.y1;
		sZ = b.z1;
		dimX = dim;
		dimY = dim;
		dimZ = dim;
		//scale=1f/dim;
		nX = (int) (b.getDimX() / dim) + 1;
		nY = (int) (b.getDimY() / dim) + 1;
		nZ = (int) (b.getDimZ() / dim) + 1;
		System.out.println("nX: " + nX + " nY: " + nY + " nZ: " + nZ);
		cubes = new DualCube[nX][nY][nZ];
		init(nX, nY, nZ);
		/*
		 * for (int x = 0; x < nX; x++) { for (int y = 0; y < nY; y++) { for
		 * (int z = 0; z < nZ; z++) { DualCube dc = new DualCube();
		 * cubes[x][y][z]=dc; dc.edges = new DualEdge[3]; } } }
		 */

	}

	public void init(int nX, int nY, int nZ) {
		cubes = new DualCube[nX][nY][nZ];
		for (int x = 0; x < nX; x++) {
			for (int y = 0; y < nY; y++) {
				for (int z = 0; z < nZ; z++) {
					DualCube dc = new DualCube();
					dc.x = (short) x;
					dc.y = (short) y;
					dc.z = (short) z;
					dc.edges = new DualEdge[3];
					cubes[x][y][z] = dc;
				}
			}
		}
	}

	public DualEdge getEdge(int x1, int y1, int z1, int x2, int y2, int z2) {
		int sX = Math.min(x1, x2);
		int sY = Math.min(y1, y2);
		int sZ = Math.min(z1, z2);
		
		DualCube dc1 = cubes[sX][sY][sZ];
		if (dc1 == null) {
			return null;
		}
		if (x1 != x2) {
			return dc1.edges[0];
		}
		if (y1 != y2) {
			return dc1.edges[1];
		}
		return dc1.edges[2];
	}

	public DualEdge addEdge(int x1, int y1, int z1, int x2, int y2, int z2) {
		int sX = Math.min(x1, x2);
		int sY = Math.min(y1, y2);
		int sZ = Math.min(z1, z2);

		int eX = Math.max(x1, x2);
		int eY = Math.max(y1, y2);
		int eZ = Math.max(z1, z2);
		DualCube dc1 = cubes[sX][sY][sZ];
		if (dc1 == null) {
			dc1 = new DualCube();
			dc1.edges = new DualEdge[3];
			cubes[sX][sY][sZ] = dc1;
		}
		if (eX >= nX || eY >= nY || eZ >= nZ)
			return null;
		DualCube dc2 = cubes[eX][eY][eZ];
		if (dc2 == null) {
			dc2 = new DualCube();
			dc2.edges = new DualEdge[3];
			cubes[eX][eY][eZ] = dc2;
		}
		DualEdge dualEdge = new DualEdge(dc1, dc2);
		if (x1 != x2) {
			dc1.edges[0] = dualEdge;
		}

		if (y1 != y2) {
			dc1.edges[1] = dualEdge;
		}
		if (z1 != z2) {
			dc1.edges[2] = dualEdge;
		}
		return dualEdge;
	}

	int getXInt(float x) {
		float f= ((x - sX) / dimX);
		return (int) f;
	}

	int getYInt(float y) {
		return (int) ((y - sY) / dimY);
	}

	int getZInt(float z) {
		return (int) ((z - sZ) / dimZ);
	}

	public float getXFloat(float x) {
		return sX + x * dimX;
	}

	public float getYFloat(float y) {
		return sY + y * dimY;
	}

	public float getZFloat(float z) {
		return sZ + z * dimZ;
	}

	Vector<SimpleTriangle> triangles;

	public void scanTriangle(HasPos3D p1, HasPos3D p2, HasPos3D p3) {
		
		TriangleMath tri=new TriangleMath(p1,p2,p3);
		/*scanX(b3d, p1, p2, p3);
		scanY(b3d, p1, p2, p3);
		scanZ(b3d, p1, p2, p3);*/
		scanX2(tri);
		scanY2(tri);
		scanZ2(tri);
	}

	
	
	final static double SMALL_NUM = 0.0000000001f;

	
	public void scanX2(TriangleMath tri) {
		int y1 = Math.max(getYInt(tri.b3d.y1),0);
		int z1 = Math.max(getZInt(tri.b3d.z1),0);
		int y2 = Math.min(getYInt(tri.b3d.y2) + 2, nY);
		int z2 = Math.min(getZInt(tri.b3d.z2) + 2, nZ);// ok

		for (int y = y1; y < y2; y++) {
			for (int z = z1; z < z2; z++) {
				float fY = getYFloat(y);
				float fZ = getZFloat(z);
				HasPos3D r0 = new Vec3D(0, fY, fZ);
				HasPos3D r1 = new Vec3D(1f, fY, fZ);// ok
				Vec3D iP = tri.intersect_LineTriangle(r0, r1);
				if (iP != null) {
					int cX = getXInt(iP.x);
					DualEdge cEdge = addEdge(cX, y, z, cX + 1, y, z);
					if (cEdge != null) {
						cEdge.intersection = iP;
						cEdge.normal = tri.n;
					}
				}
			}
		}
	}

	public void scanY2(TriangleMath tri) {
		int x1 = Math.max(getXInt(tri.b3d.x1),0);
		int z1 = Math.max(getZInt(tri.b3d.z1),0);
		int x2 = Math.min(getXInt(tri.b3d.x2) + 2, nX);
		int z2 = Math.min(getZInt(tri.b3d.z2) + 2, nZ);// ok

		for (int x = x1; x < x2; x++) {
			for (int z = z1; z < z2; z++) {
				float fX = getXFloat(x);
				float fZ = getZFloat(z);
				HasPos3D r0 = new Vec3D(fX, 0, fZ);
				HasPos3D r1 = new Vec3D(fX, 1f, fZ);
				Vec3D iP = tri.intersect_LineTriangle(r0, r1);
				if (iP != null) {
					int cY = getYInt(iP.y);
					DualEdge cEdge = addEdge(x, cY, z, x, cY + 1, z);
					if (cEdge != null) {
						cEdge.intersection = iP;
						cEdge.normal = tri.n;
					}
				}
			}
		}
	}

	public void scanZ2(TriangleMath tri) {
		int x1 = Math.max(getXInt(tri.b3d.x1), 0);
		int y1 = Math.max(getYInt(tri.b3d.y1), 0);
		int x2 = Math.min(getXInt(tri.b3d.x2) + 2, nX);
		int y2 = Math.min(getYInt(tri.b3d.y2) + 2, nY);// ok

		for (int x = x1; x < x2; x++) {
			for (int y = y1; y < y2; y++) {
				float fX = getXFloat(x);
				float fY = getYFloat(y);
				HasPos3D r0 = new Vec3D(fX, fY, 0);
				HasPos3D r1 = new Vec3D(fX, fY, 1f);
				Vec3D iP = tri.intersect_LineTriangle(r0, r1);
				if (iP != null) {
					int cZ = getZInt(iP.z);
					DualEdge cEdge = addEdge(x, y, cZ, x, y, cZ + 1);
					if (cEdge != null) {
						cEdge.intersection = iP;
						cEdge.normal = tri.n;
					}
				}
			}
		}
	}
	
	

	
	public Vector<SimpleTriangle> getFaces() {
		triangles = new Vector<SimpleTriangle>();

		for (int x = 0; x < nX - 1; x++) {
			System.out.println("x: " + x + "/" + nX);
			for (int y = 0; y < nY - 1; y++) {
				for (int z = 0; z < nZ - 1; z++) {
					DualCube cube = cubes[x][y][z];
					if (cube != null) {
						computeCubes(x, y, z);
					}
				}
			}
		}

		for (int x = 0; x < nX - 1; x++) {
			for (int y = 0; y < nY - 1; y++) {
				for (int z = 0; z < nZ - 1; z++) {
					if (cubes[x][y][z] != null) {
						generateQuads(x, y, z);
					}
				}
			}
		}
		return triangles;
	}
	public Vector<SimpleTriangle> getFaces(DualCube[][][] cubes,float iso) {
		this.cubes=cubes;
		nX=cubes.length;
		nY=cubes[0].length;
		nZ=cubes[0][0].length;
		
		

		for (int x = 0; x < nX - 1; x++) {
			System.out.println("x: " + x + "/" + nX);
			for (int y = 0; y < nY - 1; y++) {
				for (int z = 0; z < nZ - 1; z++) {
					DualCube cube = cubes[x][y][z];
					if (cube != null) {
						computeCubesByValues(x, y, z,iso);
					}
				}
			}
		}
		triangles = new Vector<SimpleTriangle>();
		for (int x = 0; x < nX - 1; x++) {
			for (int y = 0; y < nY - 1; y++) {
				for (int z = 0; z < nZ - 1; z++) {
					if (cubes[x][y][z] != null) {
						generateQuads(x, y, z);
					}
				}
			}
		}
	
		return triangles;
	}
	public Vector<SimpleTriangle> getFaces(float[][][] values,float iso) {
		nX=values.length;
		nY=values[0].length;
		nZ=values[0][0].length;
		cubes = new DualCube[nX][nY][nZ];
		for (int x = 0; x < nX; x++) {
			for (int y = 0; y < nY; y++) {
				for (int z = 0; z < nZ; z++) {
					DualCube dc = new DualCube();
					dc.x = (short) x;
					dc.y = (short) y;
					dc.z = (short) z;
					dc.edges = new DualEdge[3];
					dc.value=values[x][y][z];
					cubes[x][y][z] = dc;
				}
			}
		}

		for (int x = 0; x < nX - 1; x++) {
			System.out.println("x: " + x + "/" + nX);
			for (int y = 0; y < nY - 1; y++) {
				for (int z = 0; z < nZ - 1; z++) {
					DualCube cube = cubes[x][y][z];
					if (cube != null) {
						computeCubesByValues(x, y, z,iso);
					}
				}
			}
		}
		triangles = new Vector<SimpleTriangle>();
		for (int x = 0; x < nX - 1; x++) {
			for (int y = 0; y < nY - 1; y++) {
				for (int z = 0; z < nZ - 1; z++) {
					if (cubes[x][y][z] != null) {
						generateQuads(x, y, z);
					}
				}
			}
		}
	
		return triangles;
	}

	public void calculateDepthWrong(boolean[][][] reached) {
		int nX = reached.length;
		int nY = reached[0].length;
		int nZ = reached[0][0].length;
		for (int z = 0; z < nZ - 1; z++) {
			for (int y = 0; y < nY - 1; y++) {
				for (int x = 0; x < nX - 1; x++) {
					boolean cDepth = reached[x][y][z];
					if (cDepth) {
						if (getEdge(x, y, z, x, y, z + 1) == null)
							reached[x][y][z + 1] = true;
						if (getEdge(x, y, z, x, y + 1, z) == null)
							reached[x][y + 1][z] = true;
						if (getEdge(x, y, z, x + 1, y, z) == null)
							reached[x + 1][y][z] = true;
					}
				}
			}
		}
		for (int z = nZ - 1; z > 0; z--) {

			for (int y = nY - 1; y > 0; y--) {
				for (int x = nX - 1; x > 0; x--) {
					boolean cDepth = reached[x][y][z];
					if (cDepth) {
						if (getEdge(x, y, z, x, y, z - 1) == null)
							reached[x][y][z - 1] = true;
						if (getEdge(x, y, z, x, y - 1, z) == null)
							reached[x][y - 1][z] = true;
						if (getEdge(x, y, z, x - 1, y, z) == null)
							reached[x - 1][y][z] = true;
					}
				}
			}
		}

	}

	public void calculateDepth(boolean[][][] reached) {
		Vector<DualCube> candidates = new Vector<DualCube>();
		for (int x = 0; x < nX - 1; x++) {
			for (int y = 0; y < nY - 1; y++) {
				for (int z = 0; z < nZ - 1; z++) {
					boolean cDepth = reached[x][y][z];
					if (cDepth) {
						DualCube dc = cubes[x][y][z];
						candidates.add(dc);
						dc.setInside(true);
					}
				}
			}
		}
		while (candidates.size() > 0) {
			Vector<DualCube> nextCandidates = new Vector<DualCube>();
			for (int i = 0; i < candidates.size(); i++) {
				DualCube cube = candidates.get(i);
				int x = cube.x;
				int y = cube.y;
				int z = cube.z;
				Vector<DualCube> nbs = new Vector<DualCube>();
				if (x < nX - 1)
					nbs.add(cubes[x + 1][y][z]);
				if (x > 0)
					nbs.add(cubes[x - 1][y][z]);
				if (y < nY - 1)
					nbs.add(cubes[x][y + 1][z]);
				if (y > 0)
					nbs.add(cubes[x][y - 1][z]);
				if (z < nZ - 1)
					nbs.add(cubes[x][y][z + 1]);
				if (z > 0)
					nbs.add(cubes[x][y][z - 1]);
				for (int j = 0; j < nbs.size(); j++) {
					DualCube nb = nbs.get(j);
					//&& getEdge(x, y, z, nb.x, nb.y, nb.z) == null
					if (!nb.isInside()) {
						if (getEdge(x, y, z, nb.x, nb.y, nb.z) == null){
							nb.setInside(true);
							boolean isBorder=this.isBorder(nb.x, nb.y, nb.z);
							//if (!isBorder){
							nextCandidates.add(nb);
							//}
						}
					}
					/*if (!nb.isInside()
							&& getEdge(x, y, z, nb.x, nb.y, nb.z) == null) {
						nb.setInside(true);
						nextCandidates.add(nb);
					}*/
				}
			}
			candidates = nextCandidates;
		}
	}

	public boolean isBorder(int x, int y, int z) {
		DualCube dC = cubes[x][y][z];
		DualCube[] nbs = new DualCube[6];
		nbs[0] = getCube(x + 1,y,z);
		nbs[1] = getCube(x,y + 1,z);
		nbs[2] = getCube(x - 1,y,z);
		nbs[3] = getCube(x,y - 1,z);
		nbs[4] =  getCube(x,y,z - 1);
		nbs[5] =  getCube(x,y,z + 1);
		int nE = 0;
		for (int i = 0; i < 6; i++) {
			DualCube nb = nbs[i];
			if (nb != null) {
				DualEdge dE = getEdge(dC.x, dC.y, dC.z, nb.x, nb.y, nb.z);
				if (dE != null) {
					nE++;
				}
			}
		}
		if (nE > 0)
			return true;
		return false;
	}
	public DualCube getCube(int x, int y, int z) {
		if (x >= nX || y >= nY || z >= nZ||x<0||y<0||z<0)
			return null;
		return cubes[x][y][z];
	}
	public Vec3D getCenter(DualCube[] corners ){
		DualCube c1=corners[0];
		return new Vec3D(c1.x+0.5f,c1.y+0.5f,c1.z+0.5f);
	}
	public void adaptCube(DualCube cube) {
		int x = cube.x;
		int y = cube.y;
		int z = cube.z;
		DualEdge[] edges = new DualEdge[12];
		edges[0] = getEdge(x, y, z, x + 1, y, z);
		edges[1] = getEdge(x + 1, y, z, x + 1, y + 1, z);
		edges[2] = getEdge(x + 1, y + 1, z, x, y + 1, z);
		edges[3] = getEdge(x, y + 1, z, x, y, z);

		edges[4] = getEdge(x, y, z + 1, x + 1, y, z + 1);
		edges[5] = getEdge(x + 1, y, z + 1, x + 1, y + 1, z + 1);
		edges[6] = getEdge(x + 1, y + 1, z + 1, x, y + 1, z + 1);
		edges[7] = getEdge(x, y + 1, z + 1, x, y, z + 1);

		edges[8] = getEdge(x, y, z, x, y, z + 1);
		edges[9] = getEdge(x + 1, y, z, x + 1, y, z + 1);
		edges[10] = getEdge(x + 1, y + 1, z, x + 1, y + 1, z + 1);
		edges[11] = getEdge(x, y + 1, z, x, y + 1, z + 1);

		Vector<Plane> planes = new Vector<Plane>();
		Vec3D massPt = new Vec3D(getXFloat(x)+dimX*0.5f,getYFloat(y)+dimY*0.5f,getZFloat(z)+dimZ*0.5f);
		for (int i = 0; i < edges.length; i++) {
			DualEdge edge = edges[i];
			if (edge != null && edge.intersection != null) {
				Plane plane = new Plane(edge.intersection, edge.normal);
				massPt.add(edge.intersection);
				planes.add(plane);
			}
		}
		if (planes.size()>0){
		massPt.mult(1f / (planes.size()+1));
		}
		Vec3D centerPt = new Vec3D(massPt);
		Vec3D moveVec = new Vec3D();
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < planes.size(); j++) {
				Plane plane = planes.get(j);
				Vec3D planePt = plane.getPlanePoint(centerPt);
				Vec3D planeV = Vec3D.sub(planePt, centerPt);
				planeV.mult(0.5f);
				moveVec.add(planeV);
			}
			// moveVec.mult(1f/planes.size());
			Vec3D massVec = Vec3D.sub(massPt, centerPt);
			massVec.mult(0.5f);
			// moveVec.add(massVec);
			if (planes.size()>0){
			moveVec.mult(1f / ((planes.size())));
			}
			// moveVec.mult(1f/2f);
			centerPt.add(moveVec);
		}
		cube.node = centerPt;
	}
	public void adaptCube2(DualCube cube,Vec3D[]inters,Vec3D[]normals) {
		int x = cube.x;
		int y = cube.y;
		int z = cube.z;
		

		Vector<Plane> planes = new Vector<Plane>();
		Vec3D massPt = new Vec3D(x+0.5f,y+0.5f,z+0.5f);
		for (int i = 0; i < 12; i++) {
			Vec3D inter=inters[i];
			Vec3D normal=normals[i];
			if (inter != null && normal != null) {
				Plane plane = new Plane(inter, normal);
				massPt.add(inter);
				planes.add(plane);
			}
		}
		if (planes.size()>0){
		massPt.mult(1f / (planes.size()+1));
		}
		Vec3D centerPt = new Vec3D(massPt);
		Vec3D moveVec = new Vec3D();
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < planes.size(); j++) {
				Plane plane = planes.get(j);
				Vec3D planePt = plane.getPlanePoint(centerPt);
				Vec3D planeV = Vec3D.sub(planePt, centerPt);
				planeV.mult(0.5f);
				moveVec.add(planeV);
			}
			// moveVec.mult(1f/planes.size());
			Vec3D massVec = Vec3D.sub(massPt, centerPt);
			massVec.mult(0.5f);
			// moveVec.add(massVec);
			if (planes.size()>0){
			//moveVec.mult(1f / ((planes.size())));
			}
			// moveVec.mult(1f/2f);
			centerPt.add(moveVec);
		}
		cube.node = centerPt;
	}
	public Vec3D calculateMidPoint(int x1, int y1, int z1, int x2, int y2,
			int z2, float  v1,float v2, float iso) {
		
		Vec3D m = null;
		int dx = x2 - x1;
		int dy = y2 - y1;
		int dz = z2 - z1;
		float t = (iso - v1) / (v2 - v1);
		if (v1<iso!=v2<iso){
		//if (t >= 0 && t <= 1) {
			m = new Vec3D();
			m.x = (float) (x1 + t * dx);
			m.y = (float) (y1 + t * dy);
			m.z = (float) (z1 + t * dz);
		}
		return m;
	}
	public void computeCubesByValues(int x,int y,int z,float iso) {
		DualCube[] corners = new DualCube[8];
		corners[0] = getCube(x, y, z);
		corners[1] = getCube(x + 1, y, z);
		corners[2] = getCube(x + 1, y + 1, z);
		corners[3] = getCube(x, y + 1, z);

		corners[4] = getCube(x, y, z + 1);
		corners[5] = getCube(x + 1, y, z + 1);
		corners[6] = getCube(x + 1, y + 1, z + 1);
		corners[7] = getCube(x, y + 1, z + 1);

		int index = 0;
		int nOutside = 0;
		for (int i = 0; i < 8; i++) {
			if (corners[i].getValue() > iso) {
				index = index | (1 << i);
				nOutside++;
			}
		}
		if (nOutside==0||nOutside==8){
			corners[0].index=-1;
			return; // no Intersections
		}
		
		
		corners[0].index = index;
		DualEdge[] edges = new DualEdge[12];
		Vec3D[] points = new Vec3D[12];
		Vec3D[] normals = new Vec3D[12];

		int numIntersections = 0;

		int[][]edgeId=new int[12][];
		edgeId[0]=new int[]{x, y, z, x + 1, y, z};
		edgeId[1]=new int[]{x + 1, y, z, x + 1, y + 1, z};
		edgeId[2]=new int[]{x + 1, y + 1, z, x, y + 1, z};
		edgeId[3]=new int[]{x, y + 1, z, x, y, z};

		edgeId[4]=new int[]{x, y, z + 1, x + 1, y, z + 1};
		edgeId[5]=new int[]{x + 1, y, z + 1, x + 1, y + 1, z + 1};
		edgeId[6]=new int[]{x + 1, y + 1, z + 1, x, y + 1, z + 1};
		edgeId[7]=new int[]{x, y + 1, z + 1, x, y, z + 1};

		edgeId[8]=new int[]{x, y, z, x, y, z + 1};
		edgeId[9]=new int[]{x + 1, y, z, x + 1, y, z + 1};
		edgeId[10]=new int[]{x + 1, y + 1, z, x + 1, y + 1, z + 1};
		edgeId[11]=new int[]{x, y + 1, z, x, y + 1, z + 1};

		Vec3D massPoint = new Vec3D();
		Vec3D[]interPts=new Vec3D[12];
		Vec3D[]allNormals=new Vec3D[12];
		int edgeInfo = EDGETABLE[index];

		for (int i = 0; i < 12; i++) {
			
			if ((edgeInfo & (1 << i)) != 0) {
				//DualEdge edge = edges[i];
				//if (edge != null) {
					numIntersections++;
					int[]eIds=edgeId[i];
					DualCube c1 = cubes[eIds[0]][eIds[1]][eIds[2]];
					DualCube c2 = cubes[eIds[3]][eIds[4]][eIds[5]];
					Vec3D inter = calculateMidPoint(c1.x, c1.y, c1.z, c2.x,
							c2.y, c2.z, c1.getValue(), c2.getValue(), iso);
					massPoint.add(inter);
					interPts[i] = inter;
					DualCube outerCube = c1;
					if (c2.getValue() > c1.getValue()) {
						outerCube = c2;
					}
					Vec3D n = outerCube.normal;
					if (outerCube.normal == null) {
						
						n = new Vec3D(c2.x - c1.x, c2.y - c1.y, c2.z - c1.z);
					}
					else if (c1.normal!=null&&c2.normal!=null){
						//n = Vec3D.add(c1.normal, c2.normal);
						//n.mult(0.5f);
					}
					
					allNormals[i] = n;
				//}
			}

		}
		massPoint.div((float) numIntersections);
		
		double[][] matrix = new double[12][3];// davor war 12=numIntersections
		double[] vector = new double[numIntersections];
		int rows = 0;

		for (int i = 0; i < 12; ++i) {
			DualEdge edge = edges[i];
			
			if ((edgeInfo & (1 << i)) == 0) {
				continue;
			}
			//if (edge!=null){
			Vec3D normal = allNormals[i];
			matrix[rows][0] = normal.getX();
			matrix[rows][1] = normal.getY();
			matrix[rows][2] = normal.getZ();
			Vec3D p = Vec3D.sub(interPts[i], massPoint);// should be between 0 nd 1

			vector[rows] = Vec3D.dot3D(normal, p);
			rows++;
			//}
		
		}
		Vec3D newPoint = new Vec3D();

		// 
		
		
		//if (rows > 0||cubes[x][y][z]!=null) {
			QEF qef=new QEF();


			qef.evaluate(matrix, vector, rows, newPoint);
			//newPoint.mult(dimX);// scaling it back

			//System.out.println("newPoint: "+newPoint);
			newPoint.add(massPoint);
			cubes[x][y][z].node = newPoint;
			//adaptCube2(cubes[x][y][z],interPts,allNormals);
		//adaptCube(cubes[x][y][z]);
	}
	
	public void computeCubes(int x, int y, int z) {
		DualCube[] corners = new DualCube[8];
	
		corners[0] = getCube(x, y, z);
		corners[1] = getCube(x + 1, y, z);
		corners[2] = getCube(x + 1, y + 1, z);
		corners[3] = getCube(x, y + 1, z);

		corners[4] = getCube(x, y, z + 1);
		corners[5] = getCube(x + 1, y, z + 1);
		corners[6] = getCube(x + 1, y + 1, z + 1);
		corners[7] = getCube(x, y + 1, z + 1);

		int index = 0;
		for (int i = 0; i < 8; i++) {
			if (!corners[i].isInside()) {
				index = index | (1 << i);
			}
		}
		
		corners[0].index = index;

		DualEdge[] edges = new DualEdge[12];
		Vec3D[] points = new Vec3D[12];
		Vec3D[] normals = new Vec3D[12];

		int numIntersections = 0;

		int edgeInfo = EDGETABLE[index];
		edges[0] = getEdge(x, y, z, x + 1, y, z);
		edges[1] = getEdge(x + 1, y, z, x + 1, y + 1, z);
		edges[2] = getEdge(x + 1, y + 1, z, x, y + 1, z);
		edges[3] = getEdge(x, y + 1, z, x, y, z);

		edges[4] = getEdge(x, y, z + 1, x + 1, y, z + 1);
		edges[5] = getEdge(x + 1, y, z + 1, x + 1, y + 1, z + 1);
		edges[6] = getEdge(x + 1, y + 1, z + 1, x, y + 1, z + 1);
		edges[7] = getEdge(x, y + 1, z + 1, x, y, z + 1);

		edges[8] = getEdge(x, y, z, x, y, z + 1);
		edges[9] = getEdge(x + 1, y, z, x + 1, y, z + 1);
		edges[10] = getEdge(x + 1, y + 1, z, x + 1, y + 1, z + 1);
		edges[11] = getEdge(x, y + 1, z, x, y + 1, z + 1);

		Vec3D massPoint = new Vec3D();
		for (int i = 0; i < 12; i++) {
			DualEdge edge = edges[i];
			if ((edgeInfo & (1 << i)) != 0) {
				//if (edge != null) {
					numIntersections++;
					massPoint.add(edge.intersection);
					
				//}
			}
		}
		if (numIntersections > 0) {
			massPoint.div((float) numIntersections);
			double[][] matrix = new double[12][3];
			double[] vector = new double[12];
			int rows = 0;
			for (int i = 0; i < 12; ++i) {
				DualEdge edge = edges[i];
				if ((edgeInfo & (1 << i)) == 0) {
					continue;
				}
				Vec3D normal = edge.normal;
				normal.mult(1f);
				matrix[rows][0] = normal.getX();
				matrix[rows][1] = normal.getY();
				matrix[rows][2] = normal.getZ();
				Vec3D p = Vec3D.sub(edge.intersection, massPoint);// abweichung der Intersection vom durchschnitt // zwischen 1 und 0
				//p.mult(1f/dimX);//trying to scale it
				vector[rows] = Vec3D.dot3D(normal, p);
				
				rows++;
			}
			
			Vec3D newPoint = new Vec3D();
			QEF qef = new QEF();
			qef.evaluate(matrix, vector, rows, newPoint);
			//newPoint.mult(dimX);//trying to scale it back
			if (newPoint.mag()>dimX*2){
				newPoint.setLength(dimX*2);
				System.out.println("too long");
			}
			newPoint.add(massPoint);
			cubes[x][y][z].node = newPoint;
		}
	}
	
	public void generateQuads(int x, int y, int z) {
		DualCube dc = cubes[x][y][z];
		if (dc.index<0)return;// no intersections
		DualCube[] nbs = new DualCube[4];
		nbs[0] = dc;
		int flip_if_nonzero = 0;
		
		int edgeInfo = EDGETABLE[dc.index];

		for (int i = 0; i < 3; ++i) {
			if (i == 0 && (edgeInfo & (1 << 10)) !=0) {
				nbs[1] = cubes[x + 1][y][z];
				nbs[2] = cubes[x + 1][y + 1][z];
				nbs[3] = cubes[x][y + 1][z];
				flip_if_nonzero = (dc.index & (1 << 6));
			} else if (i == 1 && (edgeInfo & (1 << 6)) !=0) {
				nbs[1] = cubes[x][y][z + 1];
				nbs[2] = cubes[x][y + 1][z + 1];
				nbs[3] = cubes[x][y + 1][z];
				flip_if_nonzero = (dc.index & (1 << 7));
			} else if (i == 2 && (edgeInfo & (1 << 5)) !=0) {
				nbs[1] = cubes[x + 1][y][z];
				nbs[2] = cubes[x + 1][y][z + 1];
				nbs[3] = cubes[x][y][z + 1];
				flip_if_nonzero = (dc.index & (1 << 5));
			} else{
				continue;
			}
			
			//if (flip_if_nonzero != 0)System.out.println("flip");
			//flip_if_nonzero=0;
			//else System.out.println("noFlip");
			for (int j = 1; j < 3; ++j) {
				int ja, jb;
				if (flip_if_nonzero != 0) {
					ja = j + 0;
					jb = j + 1;
				} else {
					ja = j + 1;
					jb = j + 0;
				}
				if (nbs[0] != null && nbs[ja] != null && nbs[jb] != null) {
					Vec3D p0 = nbs[0].node;
					Vec3D p1 = nbs[ja].node;
					Vec3D p2 = nbs[jb].node;
					if (p0 != null && p1 != null && p2 != null) {
						SimpleTriangle tri = new SimpleTriangle(p2, p1, p0);
						triangles.add(tri);
					}
				} else {
					System.out.println("no Cube");
				}
				// _mesh->addFace(face, meshPlane);
			}
		}
	}
	
	public Vector<SimpleTriangle> getMCFaces() {
		
		// collect cubes
		for (int x = 0; x < nX ; x++) {
			for (int y = 0; y < nY ; y++) {
				for (int z = 0; z < nZ ; z++) {
					DualCube[] corners = new DualCube[8];
					corners[0] = getCube(x, y, z);
					corners[1] = getCube(x + 1, y, z);
					corners[2] = getCube(x + 1, y + 1, z);
					corners[3] = getCube(x, y + 1, z);

					corners[4] = getCube(x, y, z + 1);
					corners[5] = getCube(x + 1, y, z + 1);
					corners[6] = getCube(x + 1, y + 1, z + 1);
					corners[7] = getCube(x, y + 1, z + 1);
					
					
					int caseNumber = 0;
					for (int i = 7; i > -1; i--) {
						DualCube corner=corners[i];
						if (corner!=null&&corner.isInside()) {
							caseNumber++;
						}
						if (i > 0) {
							caseNumber = caseNumber << 1;
						}
					}
					corners[0].index=caseNumber;
				}
			}
		}
		// collect faces
		Vector<SimpleTriangle> faces = new Vector<SimpleTriangle>();
		for (int x = 0; x < nX - 1; x++) {
			for (int y = 0; y < nY - 1; y++) {
				for (int z = 0; z < nZ - 1; z++) {
					DualCube c = cubes[x][y][z];
					if (c != null) {
						DualCube cX = cubes[x + 1][y][z];
						DualCube cY = cubes[x][y + 1][z];
						DualCube cZ = cubes[x][y][z + 1];
						DualCube cYZ = cubes[x][y + 1][z + 1];
						DualCube cXZ = cubes[x + 1][y][z + 1];
						DualCube cXY = cubes[x + 1][y + 1][z];

						DualEdge[] edges = new DualEdge[12];
						if (cY != null)
							edges[0] = cY.edges[0];
						if (cX != null)
							edges[1] = cX.edges[1];
						edges[2] = c.edges[0];
						edges[3] = c.edges[1];
						if (cYZ != null)
							edges[4] = cYZ.edges[0];
						if (cXZ != null)
							edges[5] = cXZ.edges[1];
						if (cZ != null)
							edges[6] = cZ.edges[0];
						if (cZ != null)
							edges[7] = cZ.edges[1];
						if (cY != null)
							edges[8] = cY.edges[2];
						if (cXY != null)
							edges[9] = cXY.edges[2];
						edges[10] = c.edges[2];
						if (cX != null)
							edges[11] = cX.edges[2];
						int nEdges=0;
						for (int i=0;i<edges.length;i++){
							DualEdge edge=edges[i];
							if (edge!=null){
								nEdges++;
							}
						}
						
						int offset = c.index * 15;
						for (int i = offset; i < offset + 15; i += 3) {
							if (faceCode[i] > -1) {
								DualEdge[] vs = new DualEdge[3];
								vs[0] = edges[faceCode[i]];
								vs[1] = edges[faceCode[i + 1]];
								vs[2] = edges[faceCode[i + 2]];
								if (vs[0]!=null&&vs[1]!=null&&vs[2]!=null){
								SimpleTriangle f = new SimpleTriangle(vs[0].intersection,vs[1].intersection,vs[2].intersection);
								faces.add(f);
								}
								
							}
						}
					}
				}
			}
		}
		return faces;
	}


	final static int EDGETABLE[] = { 0x0, 0x109, 0x203, 0x30a, 0x406, 0x50f,
			0x605, 0x70c, 0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09,
			0xf00, 0x190, 0x99, 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
			0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90, 0x230,
			0x339, 0x33, 0x13a, 0x636, 0x73f, 0x435, 0x53c, 0xa3c, 0xb35,
			0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30, 0x3a0, 0x2a9, 0x1a3,
			0xaa, 0x7a6, 0x6af, 0x5a5, 0x4ac, 0xbac, 0xaa5, 0x9af, 0x8a6,
			0xfaa, 0xea3, 0xda9, 0xca0, 0x460, 0x569, 0x663, 0x76a, 0x66,
			0x16f, 0x265, 0x36c, 0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963,
			0xa69, 0xb60, 0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff, 0x3f5,
			0x2fc, 0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
			0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55, 0x15c, 0xe5c,
			0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950, 0x7c0, 0x6c9,
			0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc, 0xfcc, 0xec5, 0xdcf,
			0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0, 0x8c0, 0x9c9, 0xac3, 0xbca,
			0xcc6, 0xdcf, 0xec5, 0xfcc, 0xcc, 0x1c5, 0x2cf, 0x3c6, 0x4ca,
			0x5c3, 0x6c9, 0x7c0, 0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f,
			0xf55, 0xe5c, 0x15c, 0x55, 0x35f, 0x256, 0x55a, 0x453, 0x759,
			0x650, 0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
			0x2fc, 0x3f5, 0xff, 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0, 0xb60,
			0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c, 0x36c, 0x265,
			0x16f, 0x66, 0x76a, 0x663, 0x569, 0x460, 0xca0, 0xda9, 0xea3,
			0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac, 0x4ac, 0x5a5, 0x6af, 0x7a6,
			0xaa, 0x1a3, 0x2a9, 0x3a0, 0xd30, 0xc39, 0xf33, 0xe3a, 0x936,
			0x83f, 0xb35, 0xa3c, 0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33,
			0x339, 0x230, 0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895,
			0x99c, 0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99, 0x190,
			0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c, 0x70c,
			0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0 };
	
	private static int faceCode[] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, 1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 11,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 1, 2, 11,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 2, 11, 0, 2, 9, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, 2, 8, 3, 2, 11, 8, 11, 9, 8, -1, -1, -1,
		-1, -1, -1, 3, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, 0, 10, 2, 8, 10, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 9,
		0, 2, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 10, 2, 1, 9,
		10, 9, 8, 10, -1, -1, -1, -1, -1, -1, 3, 11, 1, 10, 11, 3, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, 0, 11, 1, 0, 8, 11, 8, 10, 11, -1, -1,
		-1, -1, -1, -1, 3, 9, 0, 3, 10, 9, 10, 11, 9, -1, -1, -1, -1, -1,
		-1, 9, 8, 11, 11, 8, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 7,
		8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 3, 0, 7, 3,
		4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 9, 8, 4, 7, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, 4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1,
		-1, -1, -1, 1, 2, 11, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		3, 4, 7, 3, 0, 4, 1, 2, 11, -1, -1, -1, -1, -1, -1, 9, 2, 11, 9, 0,
		2, 8, 4, 7, -1, -1, -1, -1, -1, -1, 2, 11, 9, 2, 9, 7, 2, 7, 3, 7,
		9, 4, -1, -1, -1, 8, 4, 7, 3, 10, 2, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, 10, 4, 7, 10, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, 9, 0,
		1, 8, 4, 7, 2, 3, 10, -1, -1, -1, -1, -1, -1, 4, 7, 10, 9, 4, 10,
		9, 10, 2, 9, 2, 1, -1, -1, -1, 3, 11, 1, 3, 10, 11, 7, 8, 4, -1,
		-1, -1, -1, -1, -1, 1, 10, 11, 1, 4, 10, 1, 0, 4, 7, 10, 4, -1, -1,
		-1, 4, 7, 8, 9, 0, 10, 9, 10, 11, 10, 0, 3, -1, -1, -1, 4, 7, 10,
		4, 10, 9, 9, 10, 11, -1, -1, -1, -1, -1, -1, 9, 5, 4, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 5, 4, 0, 8, 3, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, 0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, 8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, 1,
		2, 11, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 0, 8, 1, 2,
		11, 4, 9, 5, -1, -1, -1, -1, -1, -1, 5, 2, 11, 5, 4, 2, 4, 0, 2,
		-1, -1, -1, -1, -1, -1, 2, 11, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1,
		-1, -1, 9, 5, 4, 2, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0,
		10, 2, 0, 8, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, 0, 5, 4, 0, 1, 5,
		2, 3, 10, -1, -1, -1, -1, -1, -1, 2, 1, 5, 2, 5, 8, 2, 8, 10, 4, 8,
		5, -1, -1, -1, 11, 3, 10, 11, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1,
		-1, 4, 9, 5, 0, 8, 1, 8, 11, 1, 8, 10, 11, -1, -1, -1, 5, 4, 0, 5,
		0, 10, 5, 10, 11, 10, 0, 3, -1, -1, -1, 5, 4, 8, 5, 8, 11, 11, 8,
		10, -1, -1, -1, -1, -1, -1, 9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, 9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1,
		0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, 1, 5, 3, 3, 5,
		7, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 7, 8, 9, 5, 7, 11, 1, 2,
		-1, -1, -1, -1, -1, -1, 11, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1,
		-1, -1, 8, 0, 2, 8, 2, 5, 8, 5, 7, 11, 5, 2, -1, -1, -1, 2, 11, 5,
		2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, 7, 9, 5, 7, 8, 9, 3, 10,
		2, -1, -1, -1, -1, -1, -1, 9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 10, -1,
		-1, -1, 2, 3, 10, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, 10, 2, 1,
		10, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, 9, 5, 8, 8, 5, 7, 11, 1,
		3, 11, 3, 10, -1, -1, -1, 5, 7, 0, 5, 0, 9, 7, 10, 0, 1, 0, 11, 10,
		11, 0, 10, 11, 0, 10, 0, 3, 11, 5, 0, 8, 0, 7, 5, 7, 0, 10, 11, 5,
		7, 10, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 11, 6, 5, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 5, 11, 6, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, 9, 0, 1, 5, 11, 6, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, 1, 8, 3, 1, 9, 8, 5, 11, 6, -1, -1, -1, -1, -1, -1, 1,
		6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 6, 5, 1, 2,
		6, 3, 0, 8, -1, -1, -1, -1, -1, -1, 9, 6, 5, 9, 0, 6, 0, 2, 6, -1,
		-1, -1, -1, -1, -1, 5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1,
		2, 3, 10, 11, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 0, 8,
		10, 2, 0, 11, 6, 5, -1, -1, -1, -1, -1, -1, 0, 1, 9, 2, 3, 10, 5,
		11, 6, -1, -1, -1, -1, -1, -1, 5, 11, 6, 1, 9, 2, 9, 10, 2, 9, 8,
		10, -1, -1, -1, 6, 3, 10, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1,
		0, 8, 10, 0, 10, 5, 0, 5, 1, 5, 10, 6, -1, -1, -1, 3, 10, 6, 0, 3,
		6, 0, 6, 5, 0, 5, 9, -1, -1, -1, 6, 5, 9, 6, 9, 10, 10, 9, 8, -1,
		-1, -1, -1, -1, -1, 5, 11, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, 4, 3, 0, 4, 7, 3, 6, 5, 11, -1, -1, -1, -1, -1, -1, 1, 9,
		0, 5, 11, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, 11, 6, 5, 1, 9, 7, 1,
		7, 3, 7, 9, 4, -1, -1, -1, 6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1,
		-1, -1, -1, 1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, 8, 4,
		7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, 7, 3, 9, 7, 9, 4, 3, 2,
		9, 5, 9, 6, 2, 6, 9, 3, 10, 2, 7, 8, 4, 11, 6, 5, -1, -1, -1, -1,
		-1, -1, 5, 11, 6, 4, 7, 2, 4, 2, 0, 2, 7, 10, -1, -1, -1, 0, 1, 9,
		4, 7, 8, 2, 3, 10, 5, 11, 6, -1, -1, -1, 9, 2, 1, 9, 10, 2, 9, 4,
		10, 7, 10, 4, 5, 11, 6, 8, 4, 7, 3, 10, 5, 3, 5, 1, 5, 10, 6, -1,
		-1, -1, 5, 1, 10, 5, 10, 6, 1, 0, 10, 7, 10, 4, 0, 4, 10, 0, 5, 9,
		0, 6, 5, 0, 3, 6, 10, 6, 3, 8, 4, 7, 6, 5, 9, 6, 9, 10, 4, 7, 9, 7,
		10, 9, -1, -1, -1, 11, 4, 9, 6, 4, 11, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, 4, 11, 6, 4, 9, 11, 0, 8, 3, -1, -1, -1, -1, -1, -1, 11, 0,
		1, 11, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, 8, 3, 1, 8, 1, 6, 8,
		6, 4, 6, 1, 11, -1, -1, -1, 1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1,
		-1, -1, -1, 3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, 0, 2,
		4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, 3, 2, 8, 2, 4,
		4, 2, 6, -1, -1, -1, -1, -1, -1, 11, 4, 9, 11, 6, 4, 10, 2, 3, -1,
		-1, -1, -1, -1, -1, 0, 8, 2, 2, 8, 10, 4, 9, 11, 4, 11, 6, -1, -1,
		-1, 3, 10, 2, 0, 1, 6, 0, 6, 4, 6, 1, 11, -1, -1, -1, 6, 4, 1, 6,
		1, 11, 4, 8, 1, 2, 1, 10, 8, 10, 1, 9, 6, 4, 9, 3, 6, 9, 1, 3, 10,
		6, 3, -1, -1, -1, 8, 10, 1, 8, 1, 0, 10, 6, 1, 9, 1, 4, 6, 4, 1, 3,
		10, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, 6, 4, 8, 10, 6, 8,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, 7, 11, 6, 7, 8, 11, 8, 9, 11,
		-1, -1, -1, -1, -1, -1, 0, 7, 3, 0, 11, 7, 0, 9, 11, 6, 7, 11, -1,
		-1, -1, 11, 6, 7, 1, 11, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, 11, 6, 7,
		11, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, 1, 2, 6, 1, 6, 8, 1, 8,
		9, 8, 6, 7, -1, -1, -1, 2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3,
		9, 7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, 7, 3, 2, 6,
		7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 3, 10, 11, 6, 8, 11,
		8, 9, 8, 6, 7, -1, -1, -1, 2, 0, 7, 2, 7, 10, 0, 9, 7, 6, 7, 11, 9,
		11, 7, 1, 8, 0, 1, 7, 8, 1, 11, 7, 6, 7, 11, 2, 3, 10, 10, 2, 1,
		10, 1, 7, 11, 6, 1, 6, 7, 1, -1, -1, -1, 8, 9, 6, 8, 6, 7, 9, 1, 6,
		10, 6, 3, 1, 3, 6, 0, 9, 1, 10, 6, 7, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, 7, 8, 0, 7, 0, 6, 3, 10, 0, 10, 6, 0, -1, -1, -1, 7, 10, 6,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 7, 6, 10, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 0, 8, 10, 7, 6, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, 0, 1, 9, 10, 7, 6, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, 8, 1, 9, 8, 3, 1, 10, 7, 6, -1, -1, -1, -1, -1, -1,
		11, 1, 2, 6, 10, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 11,
		3, 0, 8, 6, 10, 7, -1, -1, -1, -1, -1, -1, 2, 9, 0, 2, 11, 9, 6,
		10, 7, -1, -1, -1, -1, -1, -1, 6, 10, 7, 2, 11, 3, 11, 8, 3, 11, 9,
		8, -1, -1, -1, 7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, 7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, 2, 7, 6, 2,
		3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, 1, 6, 2, 1, 8, 6, 1, 9, 8,
		8, 7, 6, -1, -1, -1, 11, 7, 6, 11, 1, 7, 1, 3, 7, -1, -1, -1, -1,
		-1, -1, 11, 7, 6, 1, 7, 11, 1, 8, 7, 1, 0, 8, -1, -1, -1, 0, 3, 7,
		0, 7, 11, 0, 11, 9, 6, 11, 7, -1, -1, -1, 7, 6, 11, 7, 11, 8, 8,
		11, 9, -1, -1, -1, -1, -1, -1, 6, 8, 4, 10, 8, 6, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, 3, 6, 10, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1,
		-1, 8, 6, 10, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, 9, 4, 6, 9,
		6, 3, 9, 3, 1, 10, 3, 6, -1, -1, -1, 6, 8, 4, 6, 10, 8, 2, 11, 1,
		-1, -1, -1, -1, -1, -1, 1, 2, 11, 3, 0, 10, 0, 6, 10, 0, 4, 6, -1,
		-1, -1, 4, 10, 8, 4, 6, 10, 0, 2, 9, 2, 11, 9, -1, -1, -1, 11, 9,
		3, 11, 3, 2, 9, 4, 3, 10, 3, 6, 4, 6, 3, 8, 2, 3, 8, 4, 2, 4, 6, 2,
		-1, -1, -1, -1, -1, -1, 0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, 1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, 1, 9,
		4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, 8, 1, 3, 8, 6, 1, 8,
		4, 6, 6, 11, 1, -1, -1, -1, 11, 1, 0, 11, 0, 6, 6, 0, 4, -1, -1,
		-1, -1, -1, -1, 4, 6, 3, 4, 3, 8, 6, 11, 3, 0, 3, 9, 11, 9, 3, 11,
		9, 4, 6, 11, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 9, 5, 7, 6,
		10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 4, 9, 5, 10, 7, 6,
		-1, -1, -1, -1, -1, -1, 5, 0, 1, 5, 4, 0, 7, 6, 10, -1, -1, -1, -1,
		-1, -1, 10, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, 9, 5, 4,
		11, 1, 2, 7, 6, 10, -1, -1, -1, -1, -1, -1, 6, 10, 7, 1, 2, 11, 0,
		8, 3, 4, 9, 5, -1, -1, -1, 7, 6, 10, 5, 4, 11, 4, 2, 11, 4, 0, 2,
		-1, -1, -1, 3, 4, 8, 3, 5, 4, 3, 2, 5, 11, 5, 2, 10, 7, 6, 7, 2, 3,
		7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, 9, 5, 4, 0, 8, 6, 0, 6,
		2, 6, 8, 7, -1, -1, -1, 3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1,
		-1, 6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, 9, 5, 4, 11, 1, 6,
		1, 7, 6, 1, 3, 7, -1, -1, -1, 1, 6, 11, 1, 7, 6, 1, 0, 7, 8, 7, 0,
		9, 5, 4, 4, 0, 11, 4, 11, 5, 0, 3, 11, 6, 11, 7, 3, 7, 11, 7, 6,
		11, 7, 11, 8, 5, 4, 11, 4, 8, 11, -1, -1, -1, 6, 9, 5, 6, 10, 9,
		10, 8, 9, -1, -1, -1, -1, -1, -1, 3, 6, 10, 0, 6, 3, 0, 5, 6, 0, 9,
		5, -1, -1, -1, 0, 10, 8, 0, 5, 10, 0, 1, 5, 5, 6, 10, -1, -1, -1,
		6, 10, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, 1, 2, 11, 9, 5,
		10, 9, 10, 8, 10, 5, 6, -1, -1, -1, 0, 10, 3, 0, 6, 10, 0, 9, 6, 5,
		6, 9, 1, 2, 11, 10, 8, 5, 10, 5, 6, 8, 0, 5, 11, 5, 2, 0, 2, 5, 6,
		10, 3, 6, 3, 5, 2, 11, 3, 11, 5, 3, -1, -1, -1, 5, 8, 9, 5, 2, 8,
		5, 6, 2, 3, 8, 2, -1, -1, -1, 9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1,
		-1, -1, -1, -1, 1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, 1, 5,
		6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 3, 6, 1, 6, 11,
		3, 8, 6, 5, 6, 9, 8, 9, 6, 11, 1, 0, 11, 0, 6, 9, 5, 0, 5, 6, 0,
		-1, -1, -1, 0, 3, 8, 5, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		11, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 5,
		11, 7, 5, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 5, 11, 10, 7,
		5, 8, 3, 0, -1, -1, -1, -1, -1, -1, 5, 10, 7, 5, 11, 10, 1, 9, 0,
		-1, -1, -1, -1, -1, -1, 11, 7, 5, 11, 10, 7, 9, 8, 1, 8, 3, 1, -1,
		-1, -1, 10, 1, 2, 10, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, 0, 8,
		3, 1, 2, 7, 1, 7, 5, 7, 2, 10, -1, -1, -1, 9, 7, 5, 9, 2, 7, 9, 0,
		2, 2, 10, 7, -1, -1, -1, 7, 5, 2, 7, 2, 10, 5, 9, 2, 3, 2, 8, 9, 8,
		2, 2, 5, 11, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, 8, 2, 0, 8,
		5, 2, 8, 7, 5, 11, 2, 5, -1, -1, -1, 9, 0, 1, 5, 11, 3, 5, 3, 7, 3,
		11, 2, -1, -1, -1, 9, 8, 2, 9, 2, 1, 8, 7, 2, 11, 2, 5, 7, 5, 2, 1,
		3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 7, 0, 7,
		1, 1, 7, 5, -1, -1, -1, -1, -1, -1, 9, 0, 3, 9, 3, 5, 5, 3, 7, -1,
		-1, -1, -1, -1, -1, 9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, 5, 8, 4, 5, 11, 8, 11, 10, 8, -1, -1, -1, -1, -1, -1, 5, 0,
		4, 5, 10, 0, 5, 11, 10, 10, 3, 0, -1, -1, -1, 0, 1, 9, 8, 4, 11, 8,
		11, 10, 11, 4, 5, -1, -1, -1, 11, 10, 4, 11, 4, 5, 10, 3, 4, 9, 4,
		1, 3, 1, 4, 2, 5, 1, 2, 8, 5, 2, 10, 8, 4, 5, 8, -1, -1, -1, 0, 4,
		10, 0, 10, 3, 4, 5, 10, 2, 10, 1, 5, 1, 10, 0, 2, 5, 0, 5, 9, 2,
		10, 5, 4, 5, 8, 10, 8, 5, 9, 4, 5, 2, 10, 3, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, 2, 5, 11, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, 5,
		11, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, 3, 11, 2, 3, 5,
		11, 3, 8, 5, 4, 5, 8, 0, 1, 9, 5, 11, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2,
		-1, -1, -1, 8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, 0,
		4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, 4, 5, 8, 5,
		3, 9, 0, 5, 0, 3, 5, -1, -1, -1, 9, 4, 5, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, 4, 10, 7, 4, 9, 10, 9, 11, 10, -1, -1, -1,
		-1, -1, -1, 0, 8, 3, 4, 9, 7, 9, 10, 7, 9, 11, 10, -1, -1, -1, 1,
		11, 10, 1, 10, 4, 1, 4, 0, 7, 4, 10, -1, -1, -1, 3, 1, 4, 3, 4, 8,
		1, 11, 4, 7, 4, 10, 11, 10, 4, 4, 10, 7, 9, 10, 4, 9, 2, 10, 9, 1,
		2, -1, -1, -1, 9, 7, 4, 9, 10, 7, 9, 1, 10, 2, 10, 1, 0, 8, 3, 10,
		7, 4, 10, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, 10, 7, 4, 10, 4,
		2, 8, 3, 4, 3, 2, 4, -1, -1, -1, 2, 9, 11, 2, 7, 9, 2, 3, 7, 7, 4,
		9, -1, -1, -1, 9, 11, 7, 9, 7, 4, 11, 2, 7, 8, 7, 0, 2, 0, 7, 3, 7,
		11, 3, 11, 2, 7, 4, 11, 1, 11, 0, 4, 0, 11, 1, 11, 2, 8, 7, 4, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, 4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1,
		-1, -1, -1, -1, 4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, 4,
		0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 8, 7, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 11, 8, 11, 10, 8, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, 3, 0, 9, 3, 9, 10, 10, 9, 11, -1,
		-1, -1, -1, -1, -1, 0, 1, 11, 0, 11, 8, 8, 11, 10, -1, -1, -1, -1,
		-1, -1, 3, 1, 11, 10, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1,
		2, 10, 1, 10, 9, 9, 10, 8, -1, -1, -1, -1, -1, -1, 3, 0, 9, 3, 9,
		10, 1, 2, 9, 2, 10, 9, -1, -1, -1, 0, 2, 10, 8, 0, 10, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, 3, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, 2, 3, 8, 2, 8, 11, 11, 8, 9, -1, -1, -1, -1, -1,
		-1, 9, 11, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 3, 8,
		2, 8, 11, 0, 1, 8, 1, 11, 8, -1, -1, -1, 1, 11, 2, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, 1, 3, 8, 9, 1, 8, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, 0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, 0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 };

}